# 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
#  完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
#
#  示例 1：
# 输入：n = 12
# 输出：3
# 解释：12 = 4 + 4 + 4
#
#  示例 2：
# 输入：n = 13
# 输出：2
# 解释：13 = 4 + 9
# 1 <= n <= 10⁴
import math
import sys


class Solution:
    def numSquares2(self, n: int) -> int:
        """
        四平方和定理:任意一个正整数都可以被表示为至多四个正整数的平方和
        另外当 n = 4^k * (8m + 7) 时，n 只能被表示为四个正整数的平方和
        :param n:
        :return:
        """
        def isPerfectSquare(num: int) -> bool:
            tmp = int(math.sqrt(num))
            return tmp * tmp == num

        def checkAnswer4(num: int) -> bool:
            while num % 4 == 0:
                num /= 4
            return num % 8 == 7

        if isPerfectSquare(n):  # 如果开方得到整数，则返回1
            return 1
        else:
            for i in range(1, int(math.sqrt(n)) + 1):  # 如果等于两个数的平方数之和，返回2
                if isPerfectSquare(n - i ** 2):
                    return 2
            if checkAnswer4(n):  # n = 4^k * (8m + 7) 时，n 只能被表示为四个正整数的平方和
                return 4
        return 3  # 否则只能被表示为3个数的平方和

    def numSquares1(self, n: int) -> int:
        """
        动态规划
        :param n:
        :return:
        """
        dp = [sys.maxsize] * (n + 1)  # dp[i]表示最少需要多少个数的平方来表示整数 i
        dp[0] = 0  # n >= 1, 所以dp[0] = 0
        for i in range(1, n + 1):
            # 从 1 ~ sqrt(i) 枚举每一个j 使得 i = j^2 + (i - j^2), 而 (i - j^2)前面已经计算过了,因此只需要查表即可
            for j in range(1, int(math.sqrt(i)) + 1, 1):
                dp[i] = min(dp[i], dp[i - j ** 2] + 1)
        return dp[n]

    def numSquares(self, n: int) -> int:
        return self.numSquares2(n)


if __name__ == "__main__":
    n = 12
    # n = 13
    n = 2
    print(Solution().numSquares(n))
